package com.yun.algorithmproblem.huaweiod;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class OD340 {
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
        String s = "a3c+5*6-2";
        char[] ch = s.toCharArray();
        extracted(ch);
    }

    private static void extracted1(char[] ch) {
        Queue<Character> queue = new LinkedList<>();
        Queue<Character> res = new LinkedList<>();
        int isExpression = 0;
        for (char c : ch) {
            int cNum = priorityChar(c);
            if (queue.size() == 0) {
                if (cNum == 0) {
                    queue.offer(c);
                    isExpression = 1;
                }
            } else {
                if (isExpression == 1) {
                    if (cNum == 0) {
                        queue.offer(c);
                    } else if (cNum == 1) {
                        queue.offer(c);
                        isExpression = 2;
                    } else {
                        queue = new LinkedList<>();
                        isExpression = 0;
                    }
                } else if (isExpression == 2) {
                    if (cNum == 0) {
                        queue.offer(c);
                        isExpression = 3;
                    } else {
                        queue = new LinkedList<>();
                        isExpression = 0;
                    }
                } else {
                    if (cNum == 0) {
                        queue.offer(c);
                    } else {
                        if (queue.size() > res.size()) {
                            res = new LinkedList<>(queue);
                        }
                        if (cNum == 1) {
                            while (true) {
                                Character poll = queue.poll();
                                if (priorityChar(poll) == 1) {
                                    break;
                                }
                            }
                            queue.offer(c);
                            isExpression = 2;
                        } else {
                            queue = new LinkedList<>();
                            isExpression = 0;
                        }
                    }
                }
            }
        }
        if (isExpression == 3 && queue.size() > res.size()) {
            res = new LinkedList<>(queue);
        }
        long resNum;
        long num1 = 0;
        long num2 = 0;
        char c = '0';
        while (!res.isEmpty()) {
            char poll = res.poll();
            if (priorityChar(poll) == 1) {
                c = poll;
                break;
            }
            num1 = num1 * 10 + (poll - '0');
        }
        while (!res.isEmpty()) {
            char poll = res.poll();
            num2 = num2 * 10 + (poll - '0');
        }
        if (c == '+') {
            resNum = num1 + num2;
        } else if (c == '-') {
            resNum = num1 - num2;
        } else {
            resNum = num1 * num2;
        }
        System.out.println(resNum);
    }

    private static void extracted(char[] ch) {
        char tempCh = '0';
        boolean isExpression = false;
        Queue<Character> queue = new LinkedList<>();
        Queue<Character> res = new LinkedList<>();
        for (char c : ch) {
            int curr = priorityChar(c);
            if (queue.size() == 0) {
                if (curr == 0) {
                    queue.offer(c);
                }
            } else {
                int temp = priorityChar(tempCh);
                if (temp == 0) {
                    if (curr == 0) {
                        queue.offer(c);
                    } else if (curr == 1) {
                        tempCh = c;
                    } else {
                        if (isExpression && queue.size() > res.size()) {
                            res = new LinkedList<>(queue);
                        }
                        tempCh = '0';
                        isExpression = false;
                        queue = new LinkedList<>();
                    }
                } else {
                    if (curr == 0) {
                        queue.offer(tempCh);
                        queue.offer(c);
                        tempCh = '0';
                        isExpression = true;
                    } else {
                        if (isExpression && queue.size() > res.size()) {
                            res = new LinkedList<>(queue);
                        }
                        tempCh = '0';
                        isExpression = false;
                        queue = new LinkedList<>();
                    }
                }
            }
        }
        if (isExpression && queue.size() > res.size()) {
            res = new LinkedList<>(queue);
        }
        Queue<String> infix = charToString(res);
        Queue<String> suffix = infixToSuffix(infix);
        int num=evalRPN(suffix);
        System.out.println(num);
    }

    private static int priorityChar(char c) {
        if ('0' <= c && c <= '9') {
            return 0;
        }
        if (c == '+' || c == '-' || c == '*') {
            return 1;
        }
        return 2;
    }

    private static Queue<String> charToString(Queue<Character> res) {
        LinkedList<String> infix = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        while (!res.isEmpty()) {
            char c = res.poll();
            switch (c) {
                case '+', '-', '*', '/' -> {
                    infix.offer(sb.toString());
                    sb.setLength(0);
                    infix.offer(Character.toString(c));
                }
                default -> {
                    sb.append(c);
                }
            }
        }
        infix.offer(sb.toString());
        return infix;
    }

    /*
        1.遇到非运算符,直接拼串
        2.遇到+ - * /
            -它的优先级比栈顶运算符高,入栈
            -否则把栈里优先级>=它 的都出栈,它再入栈
        3.遍历完成,栈里剩余运算符依次出栈
        4.带()
            -左括号直接入栈,左括号优先级设置为0
            -右括号就把栈里到左括号为止的所有运算符出栈
     */
    private static int priority(String c) {
        return switch (c) {
            case "*", "/" -> 2;
            case "+", "-" -> 1;
            case "(" -> 0;
            default -> throw new IllegalArgumentException("不合法的运算符:" + c);
        };
    }

    private static Queue<String> infixToSuffix(Queue<String> res) {
        LinkedList<String> stackOperator = new LinkedList<>();
        LinkedList<String> queueSuffix = new LinkedList<>();
        while (!res.isEmpty()) {
            String c = res.poll();
            switch (c) {
                case "*", "/", "+", "-" -> {
                    if (stackOperator.isEmpty()) {
                        stackOperator.push(c);
                    } else {
                        if (priority(c) > priority(stackOperator.peek())) {
                            stackOperator.push(c);
                        } else {
                            while (!stackOperator.isEmpty() && priority(stackOperator.peek()) >= priority(c)) {
                                queueSuffix.offer(stackOperator.pop());
                            }
                            stackOperator.push(c);
                        }
                    }
                }
                case "(" -> {
                    stackOperator.push(c);
                }
                case ")" -> {
                    while (!stackOperator.isEmpty() && !Objects.equals(stackOperator.peek(), "(")) {
                        queueSuffix.offer(stackOperator.pop());
                    }
                    stackOperator.pop();
                }
                default -> {
                    queueSuffix.offer(c);
                }
            }
        }
        while (!stackOperator.isEmpty()) {
            queueSuffix.offer(stackOperator.pop());
        }
        return queueSuffix;
    }

    private static int evalRPN(Queue<String> suffix) {
        int count=0;
        LinkedList<Integer> stack = new LinkedList<>();
        while (!suffix.isEmpty()) {
            String c = suffix.poll();
            switch (c) {
                case "+" -> {
                    Integer b=stack.pop();
                    Integer a=stack.pop();
                    stack.push(a+b);
                }
                case "-" -> {
                    Integer b=stack.pop();
                    Integer a=stack.pop();
                    stack.push(a-b);
                }
                case "*" -> {
                    Integer b=stack.pop();
                    Integer a=stack.pop();
                    stack.push(a*b);
                }
                case "/" -> {
                    Integer b=stack.pop();
                    Integer a=stack.pop();
                    stack.push(a/b);
                }
                default -> {
                    stack.push(Integer.parseInt(c));
                }
            }
        }
        return stack.pop();
    }
}
